

# 此处要学习几个函数
"""
heappush: 将元素推入堆中
heappop: 弹出并返回堆中最小的元素
heappushpop: 将一个新元素推入堆中，弹出并返回堆中的最小值

"""
from heapq import heappop, heappushpop, heappush

class MedianFinder:

    def __init__(self):
        self.left = [] # 存储较小的一半数
        self.right = [] # 存储较大的一半数

    def addNum(self, num: int) -> None:
        if len(self.left) == len(self.right):

            # 使用负数实现， 弹出去的相反数就是最大值
            heappush(self.left, -heappushpop(self.right, num)) 
        
        else:
            heappush(self.right, -heappushpop(self.left, -num))


    def findMedian(self) -> float:
        if len(self.left) > len(self.right):
            return -self.left[0]        
        return (self.right[0] - self.left[0]) / 2
        